---
title: "三国游戏"
created: 2025-11-28
tags:
  - 算法
---

# 三国游戏

## 题目 [三国游戏](https://www.acwing.com/problem/content/4968/)

![[image-66c8cf2c.png]]

## 思路分析

分三类情况讨论 魏国赢 蜀国赢 吴国赢

针对一种情况来说

魏国赢的话 应该是要a>b+c 转变成a-b-c>0

那么实际的每个事件也可以变形成对魏国赢的贡献值

![[image-d8676d85.png]]

显然这种情况下魏国是不可能赢的 三个事件对魏国获胜都是负贡献

考虑蜀国赢的情况

![[image-2bc437e9.png]]

显然 选择1，2事件可以让蜀国获胜

要选择尽可能多的事件让某国获胜

实际上就是在这些事件中选尽可能多的数 使得其总和大于0

那么贪心策略是 优先选择贡献较多的事件

那么可以把这些事件按降序排序

累加和应该会呈现一个这样的先升后降的趋势

![[image-4b000d48.png]]

我们要找到那个使得总和变成负前的最后一个事件是什么

它就是让某国获胜尽可能可以选到的最多的事件

这样做三遍 对每个国家都做一次 再在其中取个max就是最终答案

这个求得第一次变负的时候 可以联想到用前缀和 但是试了一下 确实是负优化 原本也就是一层循环用个sum累加 用前缀和也是一层循环 反而还加了一个LL数组

## 代码实现

```typescript
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100010;

int a[N],b[N],c[N],w[N];

int n;

int work(int x[],int y[],int z[])

{

    for(int i=1;i<=n;i++)

        w[i]=x[i]-y[i]-z[i];

    sort(w+1,w+n+1,greater<int>());

    int res=-1;

    LL sum=0;

    for(int i=1;i<=n;i++){

        sum+=w[i];

        if(sum>0)

            res=i;

        else

            break;

    }

    return res;

}

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    for(int i=1;i<=n;i++)

        cin>>b[i];

    for(int i=1;i<=n;i++)

        cin>>c[i];

    int res=max({work(a,b,c),work(b,a,c),work(c,a,b)});

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[哈夫曼模型|哈夫曼模型]] 🏠 [[00-刷题理模型]] ➡️ [[乘积最大|乘积最大]]